﻿#include <cstdlib>
#include <cstdio>

/*
 * 设单链表的表头指针为L，结点结构data和next两个域构成，其中data域为字符型。试设计算法判断该链表的全部n个字符是否中心对称。例如，xyx、xyyx都是中心对称的。
 *操作步骤：将前n/2个元素入栈，当访问（n/2，n]个元素时，依次弹出栈顶元素与之一一比较，直到栈空且链表元素都遍历完，则为中心对称，否则中心不对称。
 */
#define MaxSize 20
typedef struct LNode {
    char data;
    struct LNode *next;
} LNode, *LinkList;

void InitLinkList(LinkList &L) {
    L = (LNode *) malloc(sizeof(LNode));
    if (L == NULL) exit(-1);
    L->next = NULL;
}

void LinkInsert(LinkList &L, char e) {
    LNode *p = L->next;
    while (p != NULL) {
        p = p->next;
    }
    LNode *s = (LNode *) malloc(sizeof(LNode));
    s->data = e;
    s->next = NULL;
    p->next = s;
}

void TraverseLink(LinkList L) {
    LNode *p = L->next;
    while (p != NULL) {
        printf("%c\t", p->data);
        p = p->next;
    }
}

bool Symmetry_Link(LinkList L) {
    int len = 0;
    LNode *p = L->next;
    while (p != NULL) {
        len++;
        p = p->next;
    }// 统计链表长度
    p = L->next;
    char S[len / 2]; // 工作栈，用来保存链表前len/2个元素
    for (int i = 0; i < len / 2; i++) {
        S[i] = p->data;
        p = p->next;
    }
    int top = len / 2;//设置栈顶指针
    if (len % 2 == 0)
        p = p->next;  // 奇数个元素，p后移
    while (p != NULL && S[top] == p->data) {
        top--;
        p = p->next;
    }
    if (top == -1)  // 栈为空栈
        return true;
    else
        return false;
}


int main() {
    LinkList L;
    InitLinkList(L);
    LinkInsert(L, 'x');
    LinkInsert(L, 'x');
    LinkInsert(L, 'y');
    LinkInsert(L, 'x');
    LinkInsert(L, 'x');
    printf("单链表中的元素依次为：\n");
    TraverseLink(L);

    bool IsSymmetry = Symmetry_Link(L);
    printf("\n单链表是否是中心对称的？%d", IsSymmetry);
    return 0;
}


